package com.dy.数组.初级._136_只出现一次的数字;

import java.util.HashMap;
import java.util.Map;

/*
https://leetcode-cn.com/problems/single-number/submissions/
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4
 */
public class Solution {
    public static int singleNumber(int[] nums) {

        for(int i=0 ; i<nums.length ; i++){
            int count =0;
            for(int j =0 ;j<nums.length;j++){
                if(nums[i]==nums[j]){
                    count++;
                }
            }
            if(count==1){
                return nums[i];
            }

        }
        throw new IllegalArgumentException("No solution");
    }
//List  失败 。。
//    public static int singleNumber2(int[] nums) {
//
//        List<Integer> list=new  ArrayList<Integer>();
//
//        for(int i=0 ; i<nums.length ; i++){
//
//            if(list.contains(nums[i]) ){
//                list.remove(nums[i]);
//            }
//            else {
//                list.add(nums[i]);
//            }
//        }
//
//        return (int)list.get(0);
//    }

    //Hash
    public static int singleNumber3(int[] nums) {

        Map map = new HashMap();
        for(int i=0 ; i<nums.length ; i++){

            if(map.containsKey(nums[i]) ){
                map.remove(nums[i]);
            }
            else
                map.put(nums[i],i);

        }
        return (int)map.keySet().iterator().next();

    }

    //异或
    public static int singleNumber4(int[] nums) {

        int a=0;
        for(int i : nums) {
            a ^= i;
        }
        return a;

    }
}
